package 二分查找.easy;

/**
 * 1. 问题描述
 *      查找目标元素在有序数组中的索引下标，如果存在直接返回下标，如果不存在，返回目标元素在数组中的正确位置
 *      (即不破坏单调性)
 *
 * 2. 算法分析
 *      二分法
 *      我们按照之前的二分写法设置两个指针 i = 0  j = n-1  mid = i+(j-i)/2
 *      分析最终i，j的指向，如果存在直接返回mid即可，但是如果当前元素不在数组中
 *      从具体的例子分析
 *          [1,3,5,6]   target = 7
 *          i = 0  j = 3  mid = 1  arr[1]=3 < 7
 *          i = 2  j = 3  mid = 2  arr[2]=5 < 7
 *          i = 3  j = 3  mid = 3  arr[3]=6 < 7
 *          i = 4  j = 3  退出循环此时i就是目标元素正确的插入位置
 *      我们猜测最终i的指向就是正确插入的位置
 *      Proof:
 *          直接看更新操作
 *              i = mid + 1
 *              j = mid - 1
 *          当i > j时退出循环，所以最后一次比较是i == j的时候
 *          如果最后一次i == j时，arr[mid] != target
 *          1. arr[mid] < target
 *              i = mid + 1,此时如果i不是目标元素的正确插入位置，说明arr[i]与target之间还是其他的元素
 *
 *      上述所说的目的就是为了找到目标元素在数组中找到一个比目标元素小的最大元素，可以等于
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 搜索插入位置 {
    public static void main(String[] args) {

    }


    public int searchInsert(int[] nums, int target) {
        int i = 0; int j = nums.length-1;
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }
}
